from math import comb
from functools import cache


class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:

        @cache
        def f(n, x):
            if n == 0:
                return 1
            if x == 1:
                return y
            ans = f(n, x - 1)
            for i in range(1, n + 1):
                ans += comb(n, i) * y * f(n - i, x - 1)
                ans %= 1000000007
            return ans

        return f(n, x)


so = Solution()
print(so.numberOfWays(3, 3, 4))
print(so.numberOfWays(5, 2, 1))
